package com.hooper.solution.day5;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Tim Hooper
 * @version 1.0
 * @time 2023/02/01/00:00
 */
public class Solutions {
    /**
     * 169. 多数元素
     * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     * 示例 1：
     * 输入：nums = [3,2,3]
     * 输出：3
     * 示例 2：
     * 输入：nums = [2,2,1,1,1,2,2]
     * 输出：2
     */

    public int majorityElement(int[] nums) {
        //选择第一个战士
        int fighter = nums[0];
        //初始化友军数量为1
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            //若为友军，则友军数量加1
            if (fighter == nums[i]) {
                ++count;
                //若战士全部阵亡，则换队
            } else if (count == 0) {
                fighter = nums[i];
                ++count;
                //不为友军则同归一人
            } else --count;
        }
        //最终获胜的队伍
        return fighter;
    }

    /**
     * 给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下：
     * <p>
     * 使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
     * 将替换表与普通英文字母表对齐，形成对照表。
     * 按照对照表 替换 message 中的每个字母。
     * 空格 ' ' 保持不变。
     * 例如，key = "happy boy"（实际的加密密钥会包含字母表中每个字母 至少一次），据此，可以得到部分对照表（'h' -> 'a'、'a' -> 'b'、'p' -> 'c'、'y' -> 'd'、'b' -> 'e'、'o' -> 'f'）。
     * 返回解密后的消息。
     */
    public String decodeMessage_map_version(String key, String message) {
        Map<Character, Character> map = new HashMap<>();
        for (int i = 0, j = 0; i < key.length(); i++) {
            char c = key.charAt(i);
            if (c == ' ' || map.containsKey(c)) continue;
            map.put(c, (char) ('a' + j));
            j++;
        }
        StringBuilder builder = new StringBuilder(message.length());
        for (int i = 0; i < message.length(); i++) {
            if (message.charAt(i) == ' ')
                builder.append(' ');
            else
                builder.append(map.get(message.charAt(i)));
        }
        return builder.toString();
    }

    public String decodeMessage_array_version(String key, String message) {
        int[] ans = new int[26];
        int j = 0;
        for (int i = 0; i < key.length(); i++) {
            char c = key.charAt(i);
            if (c == ' ' || ans[c - 'a'] != 0) continue;
            ans[c - 'a'] = 'a' + j;
            j++;
        }

/*        StringBuilder sb = new StringBuilder(message.length());
        for (int i = 0; i < message.length(); i++) {
            char c = message.charAt(i);
            c = (c == ' ') ? c : (char)ans[c -'a'];
            sb.append(c);
        }
        return sb.toString();
*/
        //可在message原数组上修改
        char[] chars = message.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != ' ') {
                chars[i] = (char) ans[chars[i] - 'a'];
            }
        }
        return new String(chars);
    }


    /**
     * 2 的幂
     * 给你一个整数 n，请你判断该整数是否是 2 的幂次方。
     * 如果是，返回 true ；否则，返回 false 。
     */
    public boolean isPowerOfTwo(int n) {
        //2的n次幂只有高位是1，也就是说该数字的二进制只有一个1
        return n > 0 && Integer.bitCount(n) == 1;
    }
}
